package com.nowcoder.code.lcof;

import com.algorithm.model.ListNode;
import com.algorithm.model.ListNodeService;

public class JZ22 {

    public static void main(String[] args) {
        ListNode node = new JZ22().FindKthToTail3(ListNodeService.getByArray(new int[]{1, 2, 3, 4, 5}), 5);
        ListNodeService.print(node);
    }

    public ListNode FindKthToTail(ListNode pHead, int k) {
        if (pHead == null || k == 0) {
            return null;
        }


        int i = 1;
        ListNode head = pHead;
        while (head.next != null) {
            i++;
            head = head.next;
        }


        if (k > i) {
            return null;
        }
        i = i - k;
        for (; i > 0; i--) {
            pHead = pHead.next;
        }
        return pHead;

    }

    public ListNode FindKthToTail2(ListNode pHead, int k) {
        if (pHead == null || k == 0) {
            return null;
        }
        recursion(pHead, k);
        return res;
    }

    int i = 0;
    ListNode res = null;

    public void recursion(ListNode pHead, int k) {
        if (pHead == null) {
            return;
        }
        recursion(pHead.next, k);
        i++;
        if (i == k) {
            res = pHead;
        }
    }

    public ListNode FindKthToTail3(ListNode pHead, int k) {
        if (pHead == null || k == 0) {
            return null;
        }
        ListNode s = pHead;
        ListNode e = pHead;

        while (k > 0 && e != null) {
            e = e.next;
            k--;
        }

        while (e != null) {
            e = e.next;
            s = s.next;
        }

        if (k > 0) {
            return null;
        }
        return s;

    }



}
